The present invention relates to an identification scheme of a wide variety of applications based on security according to difficulty in solving discrete logarithm problems, single or multi-digital signature scheme giving message recovery, single or multi-digital signature scheme with appendix, key exchange, and blind digital signature scheme. Particularly, the present invention relates to an identification scheme which allows a prover to identify his own identity to a verifier more explicitly and prevents already used authentication information from being re-used, a key exchange scheme which uses a common secret key between two users in order not to allow an unauthorized to find it out, a digital signature scheme giving message recovery and digital signature scheme with appendix for producing a digital signature of a message recovery type or appendix type according to the size of a message to be signed, a multi-digital signature scheme for allowing multiple signers to generate digital signatures with respect to the same message and producing them in a message recovery type or appendix type according to the size of the message to be signed, and a blind digital signature scheme for producing a digital signature when a message to be signed should not be opened to the public and therefore a signer does not know the contents thereof.
During the development of science and semiconductor technology, computers have been widely spread and information exchange through computer networks has drastically increased. As a result, there is interest in protection of information such as identification of counterpart to exchange information with, the source of information exchanged, and its storage status, prior to exchange of information. As the current society has been entering the information society in which information would be recognized as goods, information to be transferred through public communication networks is becoming more important. Accordingly, damage is increasing due to illegal exposure or alteration of information.
Against these damages, there is increasing interest in protection of information circulated through communication lines such as public communication networks, and studies on protection of information are being briskly carried out.
For instance, there have been suggested identification schemes for allowing a communication counterpart or source of received data to be confirmed when information is exchanged through a variety of communication lines such as public communication networks, and digital signature schemes for enabling a signature of binary sequences coded by an originator on an electronic document in each of terminals prior to its communication processing, instead of hand-written signature on paper document. The digital signature schemes enable the source of transmitted document to be identified, as well as contents acknowledgement and whether the document is illegally altered or not.
In the identification schemes and digital signature schemes, assuming that p is a large prime number, q is another prime number for dividing p-1, g is a natural number having a remainder 1 obtained by dividing its q.sup.th power by p (.ident.g.sup.q mod p), g being between 1 and p, then g, q and p are system coefficients commonly utilized by users. If each user arbitrarily selects a numbers between 1 and q as a secret key and uses as a public key a remainder v (.ident.g.sup.-s mod p) obtained by dividing the -s.sup.th power of g by p, public coefficients used by the respective users are v, g, q and p.
It is hard to find out the secret key s from these public coefficients. Also, it is equivalent to the difficulty in calculating a solution of discrete logarithm. Numerous public key identification schemes and digital signature schemes are based on security from the fact that the discrete logarithms are difficult to calculate.
For such digital signature schemes, there may be classified into a digital signature scheme with appendix, a digital signature scheme giving message recovery, and a hybrid digital signature scheme using those methods in combination.
The digital signature scheme with appendix is a method in which a digital signature generated is attached to the end of a message to be signed. This signature is processed in pairs with the message signed. The digital signature scheme giving message recovery is to restore a message signed from a digital signature as a result of validity of the signature generated. A verifier confirms the contents of the restored message in order to verify the validity of the digital signature.
In the hybrid digital signature scheme using the appendix type and message recovery type in combination, a digital signature is generated for a message in the appendix type or message recovery type appropriately according to the length (binary bit streams) of the message signed or the purpose of the signature. For a short message, the hybrid digital signature scheme uses the message recovery method so that the data to verify the digital signature is reduced and in turn the amount of communication required is also reduced. For a long message, the appendix method is used while including information related to the message. As stated above, the hybrid digital signature scheme is characterized in adaptably generating a digital signature according to the length of a message signed.
Schnorr disclosed an identification scheme and digital signature scheme based on the security of discrete logarithm problem in 1989. The digital signature scheme suggested by Schnorr, which is a digital signature scheme with appendix, introduces a hash function to the digital signature scheme suggested by Elgamal in 1985, in order to simplify a procedure of generating and verifying digital signature. In addition, this scheme makes the generated digital signature smaller in size.
The identification scheme proposed by Schnorr uses the same algorithm structure as the digital signature scheme, and authenticates one's own identity to a communication counterpart. The identification scheme proposed by Schnorr in which a prover A authenticates his identity to a verifier B will be described now.
If the prover's system coefficients are g, q and p, the secret key is s (1&lt;s&lt;q), and the public key is v (.ident.g.sup.-S mod p), the prover A selects an arbitrary number r between 1 and q and transmits a remainder x (.ident.g.sup.r mod p) obtained by dividing the r.sup.th power of g by p to the verifier B. If x is received from the prover A, the verifier B selects an arbitrary number e between 1 and q and transmits the number e to the prover A. The prover A multiplies the secret key s by the arbitrary number e received from the verifier B and adds to this result the arbitrary number r used in the calculation of x. The prover A transmits a remainder y (.ident.r+se mod g) obtained by dividing r+se by q to the verifier B. If y is received from the prover A, the verifier B calculates a remainder x' (.ident.g.sup.Y v.sup.e mod p) obtained by dividing by p the product of the y.sup.th power of g by the e.sup.th power of v. The verifier B authenticates the validity of prover's identity by confirming whether x' and x are equal to each other.
In the digital signature scheme with appendix proposed by Schnorr, if a message to be signed is m, a signer A selects an arbitrary number r between 1 and q and calculates a. remainder x (.ident.g.sup.r mod p) obtained by dividing the r.sup.th power of g by p. The message m and the calculated x are applied to the hash function to yield e (=h(x,m)). The signer A calculates a remainder y (.ident.r+se mod q) obtained by dividing, by q, r added to the product of s by e. Then (e,y) is the digital signature with appendix for the message m. The validity of the digital signature (e,y) with appendix for the message m cane be easily verified and will be explained below.
That is, if the digital signature with appendix of the signer A for the message m is (e,y), the verifier B calculates a remainder x' (.ident.g.sup.Y v.sup.e mod p) obtained by dividing by p the product of the y.sup.th power of g by the e.sup.th power of v which is the public key of signer A. The remainder x' and the message m are applied to the hash function to yield e' (=h(x',m). The validity of the digital signature (e,y) with appendix of the signer A is verified by confirming whether e' and e are the same.
Meanwhile, Nyberg and Rueppel proposed a digital signature scheme giving message recovery based on security of discrete logarithm problem in 1993. This digital signature scheme giving message recovery produces a digital signature for a message, and in addition, if the same system coefficients are used by both communication parties, is able to produce a session key as their secret key by using the same algorithm as the digital signature. The digital signature scheme giving message recovery of N-R (Nyberg-Rueppel) will now be described.
It is assumed that the signer's system coefficients are g, q and p, the secret key is s (1&lt;s&lt;q), the public key is v (.ident.g.sup.-s mod p), and the message to be signed is m. The signer selects an arbitrary number r between 1 and q, and calculates a remainder x (.ident.mg.sup.-r mod p) obtained by dividing by p the product of the message m by the -r.sup.th power of g. The signer adds r to the secrete key s multiplied by x to yield r+sx and calculates a remainder y (.ident.r+sx mod q) obtained by dividing r+sx by q. Then (x,y) is the digital signature giving message recovery for the message m.
To verify the digital signature (x,y), the verifier calculates a remainder (.ident.xg.sup.Y v.sup.X mod p) obtained by dividing by p the product of x by the y.sup.th power of g and by the x.sup.th power of v, to recover the message m. The verifier verifies the validity of the digital signature (x,y) by confirming the contents of the recovered message m.
Now, the key exchange will be described in which a session key is produced between users using the same algorithm as N-R digital signature scheme.
It is assumed that users A and B commonly use system coefficients g, q, and p, the user A's secret key is s.sub.A, his public key is v.sub.A (.ident.g.sup.-s.sbsp.A mod p), the user B's secret key is s.sub.B, and his public key is v.sub.B (.ident.g.sup.-s.sbsp.B mod p). When a session key is intended to be produced between users A and B, user A selects arbitrary numbers R and r between 1 and q, and calculates x(.ident.g.sup.R g.sup.-r mod p) and y(.ident.r+s.sub.A mod q). The calculation results (x,y) are sent to user B. User A calculates session key K (.ident.(v.sub.B).sup.R .ident.(g.sup.-s.sbsp.B).sup.R mod p) obtained by dividing by p the R.sup.th power of user B's public key v.sub.B (.ident.g.sup.-s.sbsp.B mod p).
User B calculates g.sup.R (.ident.xg.sup.Y v.sub.A.sup.x mod p) from (x,y) received from user A, thereby restoring g.sup.R, and calculates remainder K(.ident.(g.sup.R).sup.-s.sbsp.B mod p) obtained by dividing by p the -s.sub.B .sup.th power of g.sup.R. Therefore, users A and B can generate session key K between each other through one time transmission/reception.
For another key exchange based upon security of discrete logarithm problem, there was suggested Diffe-Hellman key exchange method for generating a session key between two users. In this method, given that two users A and B use g, q and p as system coefficients, the users A and B select arbitrary numbers a and b between 1 and q, respectively, and calculate g.sup.a and g.sup.b. If they are exchanged, users A and B commonly have K(.ident.(g.sup.a).sup.b .ident.(g.sup.b).sup.a mod p).
In the conventional identification scheme, it is hard to obtain prover related information because identification is performed on basis of security of the identification scheme used, without prover's information such as identity, identification time, and user system, while the prover's identity is confirmed as proper. In the digital signature scheme message recovery, artificial redundancy is used to double the whole size of the signature and thus increase the load processed. In the appendix type, only the verification of signature is performed and obtaining signature related information is limited. In addition, the single signature scheme is hard to expand to the multi-signature schemes, the key exchanges or the blind digital signature scheme.